1. Field of the Invention
The present invention generally relates to estimating real-time travel times or traffic loads (e.g., traffic flows or densities) over a transportation or data or IP network based on limited real-time data. More specifically, a two-phase method estimates travel time over a transportation network comprising at least a first link having a real time data feed and a second link not having a real time data feed, by receiving the data feed for the first link, estimating a first travel time over the first link based at least in part on the data feed, and estimating a second travel time over the second link, also based at least in part on the data feed for the first link, as well as other known data, such as historical traffic patterns and physical parameters of the transportation network. The first phase is performed off-line, in advance, and the second phase is performed in real-time as the most recent data is received.
2. Description of the Related Art
The present invention relates to traffic networks, including at least transportation networks and data, or IP, networks. In the case of transportation networks, such as shown exemplarily in FIG. 1, showing a portion 100 of a transportation network in a city, data on the state of the network, in terms of volumes or flows, is generally not available across all links of the network at all points in time. A point in time refers to the instant at which an average volume or flow is made available for a link on the network.
Generally, 1-minute, 5-minute, 10-minute, or 15-minute average volumes or flows are provided in a real-time configuration. A real-time data feed therefore provides such short-term averages every time period. At any such period, it is typically the case that not all links have data associated with them.
Real-time sensor data is an important input into traffic management systems on networks. In practice, however, sensor data is not available on all links of a network at each instant in time, or even during each time “period”, and in some cases, data is simply not collected on all links all the time. In other cases, obtaining the data on all links at all time points would be too costly.
However, incomplete data on the state of the network makes the use of numerous traffic management and/or dissemination tools inefficient or inaccurate. Hence, it is of great interest to network managers to possess a method or system providing a consistent set of real-time data and estimates on the state of the network.
Similarly, in data or IP networks, it is typically the computation burden of obtaining the real-time flows or volumes on all links of a network that makes the data obtained limited. The limitation of the data is therefore both spatial (not covering all links at a particular point in time) and temporal (not covering a given link at all points in time).
On the other hand, many analytical tools for use with real-time data on networks require a complete picture of the network state at each time instant. An example for transportation networks is a dynamic routing algorithm. On an IP network an example is a performance analysis algorithm.
For example, U.S. Pat. No. 6,490,519, entitled “Traffic monitoring system and methods for traffic monitoring and route guidance useful therewith”, to Lapidot et al., addresses monitoring of network traffic through data from mobile communications devices. It is noted that, unlike the method of the present invention, Lapidot et al. does not involve expansion of observed data to links for which no real-time data has been collected.
The publication “Dynamic OD matrix estimation from link counts: An approach consistent with Dynamic Traffic Assignment” (Durlin and Henn, 2006) discusses real-time estimation of link flows in elementary networks. The objective is different from that of the present invention, in that the authors seek to determine dynamic OD (origin/destination) matrices rather than complete the network link volumes on a real network. The approach is similar in some ways in that it uses equilibrium assignment principles to calculate flows for unobserved links. However, there is no method for extending this beyond very simple and specialized networks.
Thus, a need exists for an accurate method to determine flows or volumes on traffic links that do not have complete capability for real-time data.